package com.algrithom.unionfind;

/**
 * 765. 情侣牵手
 */
class Solution9 {
    
    /**
     * 贪心算法
     *
     * @param row
     * @return
     */
    public static int minSwapsCouples2(int[] row){
        int ans = 0;
        for (int i = 0; i < row.length; i += 2) {
            int x = row[i];
            if (row[i + 1] == (x ^ 1)) {
                continue;
            }
            ans++;
            for (int j = i + 1; j < row.length; ++j) {
                if (row[j] == (x ^ 1)) {
                    row[j] = row[i + 1];
                    row[i + 1] = x ^ 1;
                    break;
                }
            }
        }
        return ans;
    }
    
    /**
     * 循环搜索
     *
     * @param row
     * @return
     */
    public int minSwapsCouples1(int[] row){
        int N = row.length / 2;
        int[][] couples = new int[N][2];

        for (int i = 0; i < row.length; ++i) {
            add(couples[row[i] / 2],i / 2 + 1);
        }

        int[][] adj = new int[N + 1][2];
        for (int[] couple : couples) {
            add(adj[couple[0]],couple[1]);
            add(adj[couple[1]],couple[0]);
        }

        int ans = N;
        for (int r = 1; r <= N; ++r) {
            if (adj[r][0] == 0 && adj[r][1] == 0) {
                continue;
            }

            ans--;
            int x = r, y = pop(adj[r]);
            while (y != r) {
                rem(adj[y],x);

                x = y;
                y = pop(adj[y]);
            }
        }
        return ans;
    }
    
    public void add(int[] pair,int x){
        pair[pair[0] == 0 ? 0 : 1] = x;
    }
    
    public void rem(int[] pair,int x){
        pair[pair[0] == x ? 0 : 1] = 0;
    }
    
    public int pop(int[] pair){
        int x = pair[0];
        if (x != 0) {
            pair[0] = 0;
        } else {
            x = pair[1];
            pair[1] = 0;
        }
        return x;
    }
}
